// https://leetcode.cn/problems/surrounded-regions/

// 题干：给你一个 m x n 的矩阵 board ，
//       由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

// 示例：输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
//       输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

// 碎语：注意边界上的不算，不需要被转化
//       floodFill算法，但是也需要一点的思维跳跃
//       正难则反的思想，先把边界全部扫描，最后得到的0都是内部合法
//       扫描边界的时候，来一次深度优先搜索，由于本题需要返回修改后的矩阵
//       因此可以修改值

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    int m, n;
public:
    void solve(vector<vector<char>>& board)
    {
        m = board.size(), n = board[0].size();

        // 1.把边界及其连通的O全部修改成'.'
        for (int j = 0 ; j < n ; j++){
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
        }

        for (int i = 0 ; i < m ; i++){
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }

        // 2.还原
        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                if (board[i][j] == '.') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = '.';
        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){
                dfs(board, x, y);
            }
        }
    }
};

int main()
{
    Solution sol;
    vector<vector<char>> board = {
            {'X', 'X', 'X', 'X'},
            {'X', 'O', 'O', 'X'},
            {'X', 'X', 'O', 'X'},
            {'X', 'O', 'X', 'X'}
    };

    sol.solve(board);

    for (const auto& str : board){
        for (const auto& ch : str){
            cout << ch << " ";
        }
        cout << endl;
    }
    return 0;
}